{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Time to Buy and Sell Stock III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProfit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #买卖股票的最佳时机 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组，它的第<em> </em><code>i</code> 个元素是一支给定的股票在第 <code>i</code><em> </em>天的价格。</p>\n",
    "\n",
    "<p>设计一个算法来计算你所能获取的最大利润。你最多可以完成 <strong>两笔 </strong>交易。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [3,3,5,0,0,3,1,4]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。\n",
    "     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [1,2,3,4,5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   \n",
    "     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   \n",
    "     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [7,6,4,3,1] \n",
    "<strong>输出：</strong>0 \n",
    "<strong>解释：</strong>在这个情况下, 没有交易完成, 所以最大利润为 0。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>prices = [1]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= prices.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= prices[i] <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-time-to-buy-and-sell-stock-iii](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-time-to-buy-and-sell-stock-iii](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,3,5,0,0,3,1,4]', '[1,2,3,4,5]', '[7,6,4,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #find all increase interval\n",
    "        if len(prices) == 0 or len(prices) == 1:\n",
    "            return 0\n",
    "        \n",
    "        buy_pt = 0\n",
    "        sell_pt = 0\n",
    "        total = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i-1] <= prices[i]:\n",
    "                sell_pt = i\n",
    "                if buy_pt is None:\n",
    "                    buy_pt = i - 1\n",
    "            else:\n",
    "                if buy_pt is not None:\n",
    "                    total += prices[sell_pt] - prices[buy_pt]\n",
    "                    buy_pt = None\n",
    "                    sell_pt = None\n",
    "        if buy_pt is not None:\n",
    "            total += prices[sell_pt] - prices[buy_pt]\n",
    "        return total\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "        result=0\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>prices[i-1]:\n",
    "                result+=(prices[i]-prices[i-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not len(prices):\n",
    "            return 0\n",
    "        prices.append(0)\n",
    "        minPrice = float('inf')\n",
    "        lastPrice = prices[0]\n",
    "        sumProfit = 0\n",
    "        for  price in prices:\n",
    "            if lastPrice>price:\n",
    "                minPrice = price\n",
    "                sumProfit += lastProfit\n",
    "            minPrice = min(minPrice,price)\n",
    "            profit = price - minPrice\n",
    "            lastProfit = profit\n",
    "            lastPrice = price\n",
    "        return sumProfit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        l = len(prices)\n",
    "        if l == 0 or l == 1:\n",
    "            return 0\n",
    "        result = [0] * l\n",
    "        m = [0] * l\n",
    "        m[0] = 7\n",
    "        temp = prices[0]\n",
    "        for i in range(1, l):\n",
    "            if temp >= prices[i]:\n",
    "                result[i] = result[i-1]\n",
    "                temp = min(temp, prices[i])\n",
    "                continue\n",
    "            m[i-1] = prices[i-1]\n",
    "            for h in range(i-1, -1, -1):\n",
    "                m[h] = min(m[i-1],m[h])\n",
    "                if m[h] == temp:\n",
    "                    result[i] = max(result[i], result[i-1], prices[i]-temp + (result[h-1] if h > 0 else 0))\n",
    "                    break\n",
    "                elif m[h] >= prices[i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if m[h] < prices[i]:\n",
    "                        result[i] = max(result[i], result[i-1], prices[i]-m[h]+ (result[h-1] if h > 0 else 0) )\n",
    "            temp = min(temp, prices[i])\n",
    "        return result[l-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if prices == []:\n",
    "            return 0\n",
    "        cash = 0\n",
    "        hold = -prices[0]\n",
    "        \n",
    "        for i in prices:\n",
    "            cash = max(cash,hold + i)\n",
    "            hold = max(hold,cash-i)\n",
    "        return cash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        tmp = 0\n",
    "        while i<len(prices)-1:\n",
    "            if prices[i] >=prices[i+1]:\n",
    "                a=0\n",
    "            else:\n",
    "                a=prices[i+1]-prices[i]\n",
    "            tmp += a\n",
    "            i += 1\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit = 0\n",
    "        for i in range(0, len(prices)-1):\n",
    "            if prices[i+1] > prices[i]:\n",
    "                profit += prices[i+1] - prices[i]\n",
    "        return profit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(prices);\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        s0, s1, s2 = 0, -prices[0], -prices[0]\n",
    "        \n",
    "        for i in range(n):\n",
    "            s0, s1, s2 = max(s0, s2), max(max(s0 - prices[i], s1), s2 - prices[i]), s1 + prices[i]\n",
    "        \n",
    "        return max(s0, s2);\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "        for i in range(0, len(prices)):\n",
    "            if i+1 < len(prices):\n",
    "                if prices[i+1] >= prices[i]:\n",
    "                    print(prices[i+1],prices[i])\n",
    "                    result += (prices[i+1] - prices[i])\n",
    "        return result \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(prices)<2:\n",
    "            return 0\n",
    "        \n",
    "        benefit = 0\n",
    "        buy_sold = []\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i] < prices[i+1] and len(buy_sold) == 0:\n",
    "                buy_sold.append(prices[i])\n",
    "            if prices[i] > prices[i+1] and len(buy_sold) == 1:\n",
    "                benefit += prices[i]-buy_sold.pop()\n",
    "            print(buy_sold)\n",
    "        if len(buy_sold) == 1:\n",
    "            benefit += prices[-1]-buy_sold.pop()\n",
    "                \n",
    "        return benefit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if prices==[]:\n",
    "            return 0\n",
    "        l = len(prices)\n",
    "        buy  = 0\n",
    "        sell = 1\n",
    "        now = 0\n",
    "        last = prices[0]\n",
    "        buyp = 0\n",
    "        earn =0\n",
    "        for i in range(1,l):\n",
    "            print(prices[i])\n",
    "            if prices[i-1]<prices[i] and buy == 0 :\n",
    "                print(\"buy\")\n",
    "                buy =1\n",
    "                buyp = prices[i-1]\n",
    "            if  prices[i-1]>prices[i] and buy ==1:\n",
    "                print(\"sell\")\n",
    "                buy = 0\n",
    "                earn += prices[i-1] - buyp\n",
    "            if buy ==1 and i == l-1:\n",
    "                print(\"sell\")\n",
    "                buy = 0\n",
    "                earn += prices[i] - buyp\n",
    "        return earn\n",
    "                \n",
    "                \n",
    "#             now = prices[i]\n",
    "#             print(now)\n",
    "#             if buy ==0 and sell ==1 and now <last:\n",
    "#                 print(\"buy\")\n",
    "#                 buy =1\n",
    "#                 buyp = now\n",
    "#                 sell = 0\n",
    "                \n",
    "#             if buy ==1 and (sell ==0 or i ==l-1)and buyp <now :\n",
    "#                 print(\"sell\")\n",
    "#                 sell =1\n",
    "#                 earn += now-buyp\n",
    "#                 buy = 0 \n",
    "        # return earn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:return 0\n",
    "        dp = [[0]*2 for _ in range(len(prices))]\n",
    "        dp[0][0], dp[0][1] = 0, -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\n",
    "            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        profit = [[0 for _ in range(2)] for _ in range(len(prices))]\n",
    "\n",
    "        # 0 未购买 1 已持有\n",
    "        profit[0][0], profit[0][1] = 0, -prices[0]\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "            profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i])\n",
    "            profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i])\n",
    "            res = max(res, profit[i][0], profit[i][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit0 = 0\n",
    "        profit1 = - max(prices) - 100 if len(prices) > 0 else -100\n",
    "        for price in prices:\n",
    "            p0 = max(profit0, profit1 + price)\n",
    "            p1 = max(profit1, profit0 - price)\n",
    "            profit0 = p0\n",
    "            profit1 = p1\n",
    "        return profit0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        profit = 0\n",
    "        current = prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] < prices[i - 1]:\n",
    "                profit += (prices[i - 1] - current)\n",
    "                current = prices[i]\n",
    "        profit += (prices[-1] - current)\n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        ben = 0\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i]<prices[i+1]:\n",
    "                ben+=prices[i+1]-prices[i]\n",
    "        return ben"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if prices == []: return 0\n",
    "\n",
    "        m = 0  # 累计利润\n",
    "        for i in range(1, len(prices)):\n",
    "            res = prices[i] - prices[i-1]\n",
    "            if res > 0:\n",
    "                m += res\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not len(prices):\n",
    "            return 0\n",
    "        max_profit = 0\n",
    "        for index in range(1,len(prices)):\n",
    "            if prices[index] >= prices[index-1]:\n",
    "                max_profit += (prices[index] - prices[index - 1])\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        tmp = prices[0]\n",
    "        sum = 0\n",
    "        for index in range(1, len(prices)):\n",
    "            if prices[index] > tmp:\n",
    "                sum += prices[index] - tmp\n",
    "                tmp =  prices[index]\n",
    "            else:\n",
    "                tmp = prices[index]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        dp_i_0, dp_i_1 = 0, -float('inf')\n",
    "        for i in range(n):\n",
    "            temp = dp_i_0\n",
    "            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])\n",
    "            dp_i_1 = max(dp_i_1, temp - prices[i])\n",
    "        return dp_i_0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            earned = prices[i] - prices[i - 1]\n",
    "            if earned > 0:\n",
    "                res += earned\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, lstPrice: List[int]) -> int:\n",
    "        iSum = 0\n",
    "        iBuy = -1\n",
    "        for iDay in range(len(lstPrice) - 1):\n",
    "            if lstPrice[iDay] < lstPrice[iDay + 1]:\n",
    "                if iBuy < 0:\n",
    "                    iBuy = lstPrice[iDay]\n",
    "                    continue\n",
    "            else:\n",
    "                if iBuy >= 0:\n",
    "                    iSum += lstPrice[iDay] - iBuy\n",
    "                    iBuy = -1\n",
    "        # print(iSum)\n",
    "            # if lstPrice[iDay] > lstPrice[iDay + 1]:\n",
    "            # \tiBuy = iYesterday\n",
    "        if iBuy >= 0:\n",
    "            iSum += lstPrice[-1] - iBuy\n",
    "        return iSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] > prices[i-1]:\n",
    "                res += prices[i] - prices[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        profit = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            tmp = prices[i] - prices[i - 1]\n",
    "            if tmp > 0: profit += tmp\n",
    "        return profit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        iSum = 0\n",
    "        for iDay in range(len(prices) - 1):\n",
    "            if prices[iDay + 1] > prices[iDay]:\n",
    "                iSum += prices[iDay + 1] - prices[iDay]\n",
    "        return iSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] - prices[i-1] > 0:\n",
    "                result += (prices[i] - prices[i-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        max_profit = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            profit = prices[i] - prices[i-1]\n",
    "            if profit > 0:\n",
    "                max_profit += profit\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        buy, sell = -inf, 0\n",
    "        for p in prices:\n",
    "            buy = max(buy, sell - p)\n",
    "            sell = max(sell, buy + p)\n",
    "        return sell"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        d = []\n",
    "        for i in range(1, len(prices)):\n",
    "            d = prices[i] - prices[i - 1]\n",
    "            if d > 0:\n",
    "                ans += d\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        d = []\n",
    "        for i in range(1, len(prices)):\n",
    "            d.append(prices[i] - prices[i - 1])\n",
    "        for x in d:\n",
    "            if x > 0:\n",
    "                ans += x\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n=len(prices)\n",
    "        if n==0 or n==1:\n",
    "            return 0\n",
    "        dp1=[0]*n  # sell out on last day\n",
    "        dp2=[0]*n  # buy in on last day\n",
    "        dp2[0]=-prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "\n",
    "            dp1[i]=max(dp1[i-1],dp2[i-1]+prices[i])\n",
    "            dp2[i]=max(dp2[i-1],dp1[i-1]-prices[i])\n",
    "\n",
    "        #print(dp1)\n",
    "        #print(dp2)\n",
    "        return dp1[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        total, index, length = 0, 0, len(prices)\n",
    "        while (index < length):\n",
    "            while (index < length - 1 and prices[index] >= prices[index + 1]):\n",
    "                index += 1\n",
    "            min = prices[index]\n",
    "            while (index < length - 1 and prices[index] <= prices[index + 1]):\n",
    "                index += 1\n",
    "            total += prices[index] - min\n",
    "            index += 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(prices)\n",
    "        for i in range(1, n):\n",
    "            res += max(0, prices[i] - prices[i - 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        l = len(prices)\n",
    "        if l < 2: return 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1,l):\n",
    "            profit = prices[i] - prices[i-1]\n",
    "            if profit > 0:\n",
    "                res += profit\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        stack = [prices[0]]\n",
    "        res = 0\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>=stack[-1]:\n",
    "                stack.append(prices[i])\n",
    "            else:\n",
    "                if len(stack)>=2:\n",
    "                    res +=stack[-1] -stack[0] \n",
    "                    stack = [prices[i]]\n",
    "                else:\n",
    "                    stack = [prices[i]]\n",
    "        \n",
    "        if len(stack)>=2:\n",
    "            res += stack[-1] -stack[0]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # 动态规划：第[]天进行操作/不进行操作的最大利润：那也不行，如果状态转移的话怎么知道当前是否持有？\n",
    "        # 第[]天收市的时候持有/不持有时获得的最大利润\n",
    "        dp_array = [[0] * 2] * len(prices)\n",
    "        dp_array[0][0] = -prices[0]\n",
    "        dp_array[0][1] = 0\n",
    "\n",
    "        for i, price in enumerate(prices[1:]):\n",
    "            dp_array[i][0] = max(dp_array[i-1][0], dp_array[i-1][1] - price) # price 总是正数。\n",
    "            dp_array[i][1] = max(price + dp_array[i-1][0] , dp_array[i-1][1]) # 这里是加，因为我们把买设置为负数，如果减去负数就是加上正数了。\n",
    "\n",
    "        return dp_array[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        dp = [[0] * n for i in range(2)]\n",
    "        dp[0][0] = -prices[0]                             # profit\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - prices[i])                           # hold = buy or hold old\n",
    "            dp[1][i] = max(dp[1][i - 1], prices[i] + dp[0][i - 1])                           # do not hold = sell today or do not hold old\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        buy = [0] * n\n",
    "        sell = [0] * n\n",
    "        buy[0] = -prices[0]\n",
    "        sell[0] = 0\n",
    "        for i in range(1,n):\n",
    "            buy[i] = max(sell[i-1] - prices[i], buy[i-1])\n",
    "            sell[i] = max(buy[i-1] + prices[i], sell[i-1])\n",
    "        print(buy,sell)\n",
    "        return sell[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        df = [[0] * n for i in range(2)]\n",
    "        df[1][0] = -prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            df[1][i] = max(df[1][i-1], df[0][i-1] - prices[i])\n",
    "            df[0][i] = max(df[0][i-1], prices[i] + df[1][i-1])\n",
    "        print(df)\n",
    "        return df[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [0]*len(prices)\n",
    "        for i in range(1, len(prices)+1):\n",
    "            if i == 1:\n",
    "                continue\n",
    "            else:\n",
    "                if prices[-i] >= prices[-i+1]:\n",
    "                    dp[-i] = max(dp[-i], max(dp[-i:]))\n",
    "                else:\n",
    "                    dp_tmp = dp[-i:]\n",
    "                    price_tmp = prices[-i:]\n",
    "                    res = [dp_tmp[k]+price_tmp[k]-prices[-i] for k in range(len(dp_tmp))]\n",
    "                    dp[-i] = max(max(res), dp[-i], max(dp_tmp))\n",
    "        # print(dp)\n",
    "\n",
    "        # cnt = 0\n",
    "        # ans = 0\n",
    "        # for i in dp:\n",
    "        #     if i > 0:\n",
    "        #         ans += i\n",
    "        #         cnt += 1\n",
    "        \n",
    "        # if not cnt:\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     return ans - cnt + 1\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp = [0]*len(prices)\n",
    "        # for i in range(1,len(prices)):\n",
    "        #     for j in range(i):\n",
    "        #         dp[i] = max([dp[i], dp[j], dp[j-1]+prices[i]-prices[j]])\n",
    "        # return max(dp) \n",
    "\n",
    "        dp = [(0,-prices[0])]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp.append((max(dp[-1][0], dp[-1][1]+prices[i]), max(dp[-1][1], dp[-1][0]-prices[i])))\n",
    "        return max(dp[-1])\n",
    "\n",
    "        # ans = 0\n",
    "        # for i in range(1,len(prices)):\n",
    "        #     ans += max(0, prices[i]-prices[i-1])\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices) -> int:\n",
    "        dp = [[0, 0] for i in range(len(prices))]\n",
    "        dp[0] = [-prices[0], 0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])\n",
    "            dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxProfit(self, prices: List[int]) -> int:\n",
    "#         profit = 0\n",
    "#         for i in range(1, len(prices)):\n",
    "#             tmp = prices[i] - prices[i - 1]\n",
    "#             if tmp > 0: \n",
    "#                 profit += tmp\n",
    "#         return profit\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[0,0] for _ in range(n)]\n",
    "        dp[0] = [-prices[0], 0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i-1][0], - prices[i] + dp[i-1][1])\n",
    "            dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #dp[i][0],dp[i][1]持有与不持有的状态\n",
    "        #dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])\n",
    "        #dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])\n",
    "        \n",
    "        length = len(prices)\n",
    "        dp = [[0] * 2 for _ in range(length)]\n",
    "        dp[0][0] = -prices[0]\n",
    "        dp[0][1] = 0\n",
    "        for i in range(1, length):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) \n",
    "            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        N = len(prices)\n",
    "        # 定义状态：dp[i][j]表示在第i天持有或卖出时的最大利润，j=1代表持有，j=0代表卖出\n",
    "        dp = [[0 for j in range(2)] for i in range(N)]\n",
    "\n",
    "        # badcase\n",
    "        for i in range(N):\n",
    "            # badcase\n",
    "            if i - 1 == -1:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = -prices[i]\n",
    "            else:\n",
    "                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])\n",
    "                dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])\n",
    "        return dp[N-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        len_prices = len(prices)\n",
    "        buy1, sell1, buy2, sell2 = -prices[0], 0, -prices[0], 0\n",
    "\n",
    "        for i in range(0, len_prices):\n",
    "            buy1 = max(buy1, -prices[i])\n",
    "            sell1 = max(sell1, buy1 + prices[i])\n",
    "            buy2 = max(buy2, sell1 - prices[i])\n",
    "            sell2 = max(sell2, buy2 + prices[i])\n",
    "\n",
    "        return sell2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(prices)\n",
    "        profit_forward = [0 for i in range(n + 1)]\n",
    "        profit_backward = [0 for i in range(n + 1)]\n",
    "        \n",
    "        # forward\n",
    "        minSoFar = float('inf')\n",
    "        for i in range(n):\n",
    "            if prices[i] < minSoFar:\n",
    "                minSoFar = prices[i]\n",
    "            profit_forward[i + 1] = max(profit_forward[i], prices[i] - minSoFar)\n",
    "        \n",
    "        # backward\n",
    "        maxSoFar = float('-inf')\n",
    "        for i in range(n):\n",
    "            if prices[n - 1 - i] > maxSoFar:\n",
    "                maxSoFar = prices[n - 1 - i]\n",
    "            profit_backward[n - 1 - i] = max(profit_backward[n - i], maxSoFar - prices[n - 1 - i])\n",
    "        \n",
    "        max_profit = 0\n",
    "        for i in range(n + 1):\n",
    "            if profit_forward[i] + profit_backward[i] > max_profit:\n",
    "                max_profit = profit_forward[i] + profit_backward[i]\n",
    "        return max_profit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit_start_point, profit_buy_1, profit_buy_2, profit_sell_1, profit_sell_2 = 0, float('-inf'), float('-inf'), 0, 0\n",
    "        for price in prices:\n",
    "                profit_buy_1 = max(profit_buy_1, profit_start_point - price)\n",
    "                # because -  price, max means spend min\n",
    "                profit_sell_1 = max(profit_sell_1, profit_buy_1 + price)\n",
    "                profit_buy_2 = max(profit_buy_2, profit_sell_1 - price)\n",
    "                # use money based on sell1\n",
    "                profit_sell_2 = max(profit_sell_2, profit_buy_2 + price)\n",
    "                print(profit_buy_1,profit_sell_1,profit_buy_2,profit_sell_2)\n",
    "        return profit_sell_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        max_k = 2\n",
    "        dp = [[0] * 2 for _ in range(max_k + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(n):\n",
    "            for k in range(1, max_k + 1):\n",
    "                if i == 0:\n",
    "                    dp[k][0] = 0\n",
    "                    dp[k][1] = -float('INF')\n",
    "                dp[k][0] = max(dp[k][0], dp[k][1] + prices[i])\n",
    "                dp[k][1] = max(dp[k][1], dp[k - 1][0] - prices[i])\n",
    "        return dp[max_k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])\n",
    "        # dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])\n",
    "        # dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])\n",
    "        # dp[i][1][1] = max(dp[i-1][1][1], -prices[i])\n",
    "\n",
    "        \n",
    "        dp_i10 = 0\n",
    "        dp_i11 = float('-inf') # 只需要存储四个值\n",
    "        dp_i20 = 0\n",
    "        dp_i21 = float('-inf')\n",
    "\n",
    "        for price in prices:\n",
    "            dp_i20 = max(dp_i20, dp_i21 + price) # 第二次操作之后不持股\n",
    "            dp_i21 = max(dp_i21, dp_i10 - price) # 第二次操作之后持股  买入\n",
    "            dp_i10 = max(dp_i10, dp_i11 + price) # 第一次买入之后卖出\n",
    "            dp_i11 = max(dp_i11, -price) # 第一次买入\n",
    "        \n",
    "        return dp_i20\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n <= 1: return 0\n",
    "        dp = [[0] * 3 for _ in range(n)]\n",
    "        for j in range(1, 3):\n",
    "            minCost = prices[0]\n",
    "            for i in range(1, n):\n",
    "                minCost = min(minCost, prices[i] - dp[i-1][j-1])\n",
    "                dp[i][j] = max(dp[i-1][j], prices[i] - minCost)\n",
    "        return dp[n-1][2]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        # 0 没买 1买了1次 2买了1次卖掉， 3买第二次 ， 4卖掉第二次\n",
    "        N = len(prices)\n",
    "        dp = [ [0,0,0,0,0] for _ in range(N) ]\n",
    "        dp[0][1] = - prices[0]\n",
    "        dp[0][3] = - prices[0]\n",
    "        for i in range(1, N):\n",
    "            dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])\n",
    "            dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])\n",
    "            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])\n",
    "            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])\n",
    "        #print(dp)\n",
    "        return max(dp[N-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        f = [[float(\"-inf\"),float(\"-inf\"),float(\"-inf\"),float(\"-inf\")] for _ in range(len(prices))]\n",
    "        f[0][0] = -prices[0]\n",
    "        for i in range(1,len(prices)):\n",
    "            f[i][0] = max(f[i-1][0],-prices[i])\n",
    "            f[i][1] = max(f[i-1][1], f[i-1][0] + prices[i])\n",
    "            f[i][2] = max(f[i-1][2], f[i-1][1]-prices[i])\n",
    "            f[i][3] = max(f[i-1][3], f[i-1][2]+prices[i])\n",
    "        # print(f)\n",
    "        return max(max(f[-1]),0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n =len(prices)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        dp = [ [[0, 0, 0], [0, 0, 0]]  for _ in range(n)] # dp[a][b][c] a为天数，b取（0，1）分别为未持有和持有股票，c为交易完成次数\n",
    "\n",
    "        dp[0][0][0] = 0 \n",
    "        dp[0][0][1] = float('-inf')\n",
    "        dp[0][0][2] = float('-inf')\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        dp[0][1][1] = float('-inf')\n",
    "        dp[0][1][2] = float('-inf')\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0][0] = 0 \n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])\n",
    "            dp[i][1][2] = float('-inf')\n",
    "        return max(dp[-1][0][1], dp[-1][0][2], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        buy1 = buy2 = -prices[0]\n",
    "        sell1 = sell2 = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            buy1 = max(buy1, -prices[i])\n",
    "            sell1 = max(sell1, buy1 + prices[i])\n",
    "            buy2 = max(buy2, sell1 - prices[i])\n",
    "            sell2 = max(sell2, buy2 + prices[i])\n",
    "        return sell2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n=len(prices)\n",
    "        buy1=buy2=-prices[0]\n",
    "        sell1=sell2=0\n",
    "        for i in range(1,n):\n",
    "            buy1=max(buy1,-prices[i])\n",
    "            sell1=max(sell1,buy1+prices[i])\n",
    "            buy2=max(buy2,sell1-prices[i])\n",
    "            sell2=max(sell2,buy2+prices[i])\n",
    "        return sell2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        buy1 = buy2 = -prices[0]\n",
    "        sell1 = sell2 = 0\n",
    "        for i in range(1, n):\n",
    "            buy1 = max(buy1, -prices[i])\n",
    "            sell1 = max(sell1, buy1 + prices[i])\n",
    "            buy2 = max(buy2, sell1 - prices[i])\n",
    "            sell2 = max(sell2, buy2 + prices[i])\n",
    "        return sell2\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxProfit(self, prices: List[int]) -> int:\n",
    "#         n = len(prices)\n",
    "#         dp = [[0,0,0,0] for _ in range(n)]\n",
    "#         dp[0]=[-prices[0],0,-prices[0],0]\n",
    "#         for i in range(1,n):\n",
    "#             dp[i][0] = max(dp[i-1][0], -prices[i])\n",
    "#             dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])\n",
    "#             dp[i][2] = max(dp[i-1][2], - prices[i] + dp[i-1][1])\n",
    "#             dp[i][3] = max(dp[i-1][3], + prices[i] + dp[i-1][2])\n",
    "#         return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        f1, f2, f3, f4 = -prices[0],0,-prices[0],0\n",
    "        for price in prices[1:]:\n",
    "            f1 = max(f1,-price)\n",
    "            f2 = max(f2,f1+price)\n",
    "            f3 = max(f3,f2-price)\n",
    "            f4 = max(f4,f3+price)\n",
    "        return f4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        left = [0] * n\n",
    "        mn = prices[0]\n",
    "        right = [0] * n\n",
    "        mx = prices[-1]\n",
    "        for i in range(1, n):\n",
    "            mn = min(mn, prices[i])\n",
    "            left[i] = max(left[i - 1], prices[i] - mn)\n",
    "            ii = n - 1 - i\n",
    "            mx = max(mx, prices[ii])\n",
    "            right[ii] = max(right[ii + 1], mx - prices[ii])\n",
    "        ans = right[0]\n",
    "        for i in range(n - 1):\n",
    "            ans = max(ans, left[i] + right[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        size = len(prices)\n",
    "        if size <= 1:\n",
    "            return 0\n",
    "        b1 = [0] * size\n",
    "        s1 = [0] * size\n",
    "        b2 = [0] * size\n",
    "        s2 = [0] * size\n",
    "\n",
    "        b1[0] = -1 * prices[0]\n",
    "        b2[0] = -1 * prices[0]\n",
    "\n",
    "        for i in range(1, size):\n",
    "            b1[i] = max(b1[i-1], -1 * prices[i])\n",
    "            s1[i] = max(s1[i-1], b1[i-1] + prices[i])\n",
    "            b2[i] = max(b2[i-1], s1[i-1] - prices[i])\n",
    "            s2[i] = max(s2[i-1], b2[i-1] + prices[i])\n",
    "\n",
    "        return s2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #1544\n",
    "        n=len(prices)\n",
    "        \n",
    "        dp1=[0]*n\n",
    "        dp2=[0]*n\n",
    "        \n",
    "        dp3=[0]*n\n",
    "        dp4=[0]*n\n",
    "        dp1[0]=-prices[0]\n",
    "        dp2[0]=-inf\n",
    "        dp3[0]=-inf\n",
    "        dp4[0]=-inf\n",
    "        for i in range(1,n):\n",
    "            dp1[i]=max(dp1[i-1],-prices[i])\n",
    "            dp2[i]=max(dp2[i-1],dp1[i-1]+prices[i])\n",
    "            dp3[i]=max(dp3[i-1],dp2[i-1]-prices[i])\n",
    "            dp4[i]=max(dp4[i-1],dp3[i-1]+prices[i])\n",
    "        print(dp1)\n",
    "        print(dp2)\n",
    "        print(dp3)\n",
    "        print(dp4)\n",
    "        return max(dp4[-1],dp2[-1],0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if len(prices) < 2:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0,0,0,0,0] for _ in range(len(prices))]\n",
    "        a = 0\n",
    "        b = -prices[0]\n",
    "        c = -float('inf')\n",
    "        d = -float('inf')\n",
    "        e = -float('inf')\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "            bb = max(b, a-prices[i])\n",
    "            cc = max(c, b+prices[i])\n",
    "            dd = max(d, c-prices[i])\n",
    "            ee = max(e, d+prices[i])\n",
    "            b = bb \n",
    "            c = cc \n",
    "            d = dd \n",
    "            e = ee\n",
    "        return max(a,b,c,d,e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ''' \n",
    "                  1  2  3  4  5 \n",
    "        1st hold -1 -1 -1 -1 -1\n",
    "        1st sell  0  1  2  3  4 \n",
    "        2nd hold -1 -1 -1 -1 -1 \n",
    "        2nd sell  0  1  2  3  4\n",
    "        ''' \n",
    "        dp = [[0] * len(prices) for _ in range(4)] \n",
    "\n",
    "        dp[0][0] = -prices[0] \n",
    "        dp[2][0] = -prices[0]   \n",
    "        dp[1][0] = 0 \n",
    "        dp[3][0] = 0 \n",
    "\n",
    "        for i in range(1, len(prices)): \n",
    "            dp[0][i] = max(dp[0][i-1], -prices[i]) \n",
    "            dp[1][i] = max(dp[1][i-1], dp[0][i] + prices[i]) \n",
    "            dp[2][i] = max(dp[2][i-1], dp[1][i] - prices[i]) \n",
    "            dp[3][i] = max(dp[3][i-1], dp[2][i] + prices[i]) \n",
    "        \n",
    "        print(dp)\n",
    "        return dp[-1][-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxProfit(self, prices: List[int]) -> int:\n",
    "#         fb, fs, sb, ss = float('inf'), 0, float('inf'), 0\n",
    "#         for price in prices:\n",
    "#             fb = min(fb, price)  \n",
    "#             fs = max(fs, price-fb)  \n",
    "#             sb = min(sb, price-fs) \n",
    "#             ss = max(ss, price-sb)  \n",
    "#         return ss\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[0,0,0,0] for _ in range(n)]\n",
    "        dp[0]=[-prices[0],0,-prices[0],0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = max(dp[i-1][0], -prices[i])\n",
    "            dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])\n",
    "            dp[i][2] = max(dp[i-1][2], - prices[i] + dp[i-1][1])\n",
    "            dp[i][3] = max(dp[i-1][3], + prices[i] + dp[i-1][2])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[i][1]第一次持有 = max（dp[i-1][1],-prices[i]）\n",
    "        # dp[i][2]第一次不持有 = max(dp[i-1][2],dp[i-1][1]+prices[i])\n",
    "        # dp[i][3]第二次持有 = max(dp[i-1][3],dp[i-1][2]-prices[i])\n",
    "        # dp[i][4]第二次不持有 = max(dp[i-1][4],dp[i-1][3] +prices[i])\n",
    "        n = len(prices)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [[0]*5 for _ in range(n)]\n",
    "        dp[0][1],dp[0][3], = -prices[0],-prices[0]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,n):\n",
    "            dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])\n",
    "            dp[i][2] = max(dp[i-1][2],dp[i-1][1] +prices[i])\n",
    "            dp[i][3] = max(dp[i-1][3],dp[i-1][2] -prices[i])\n",
    "            dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])\n",
    "        return dp[-1][4]\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[0] * 5 for _ in range(len(prices))]\n",
    "        dp[0] = [0, -prices[0], 0, -prices[0], 0]\n",
    "        for i, price in enumerate(prices[1:], 1):\n",
    "            for j in range(1, 5):\n",
    "                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + ((-1) ** j) * prices[i])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[0 for _ in range(5)] for _ in range(len(prices))]\n",
    "        dp[0][0], dp[0][1], dp[0][2], dp[0][3], dp[0][4] = 0, -prices[0], 0, -prices[0], 0\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][1] = max(dp[i-1][1], - prices[i])\n",
    "            dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])\n",
    "            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])\n",
    "            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])\n",
    "        return dp[-1][4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(prices)):\n",
    "           dp.append([0,0])\n",
    "        dp[0][1]=-prices[0]\n",
    "        dp1=[]\n",
    "        for i in range(len(prices)):\n",
    "           dp1.append([0,0])\n",
    "        dp1[0][1]=-prices[0]\n",
    "        for i in range(1,len(dp)):\n",
    "            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])\n",
    "            dp[i][1]=max(dp[i-1][1],-prices[i])\n",
    "            dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]+prices[i])\n",
    "            dp1[i][1]=max(dp1[i-1][1],dp[i-1][0]-prices[i])\n",
    "        return dp1[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        numslen = len(prices)\n",
    "        if numslen == 0 :\n",
    "            return 0 \n",
    "            \n",
    "        dp = [[0 for i in range(5)] for j in range(numslen)]#新建二维数组\n",
    "\n",
    "        dp[0][1] = -prices[0];\n",
    "        dp[0][3] = -prices[0];\n",
    "\n",
    "        for i in range(1, numslen):\n",
    "            dp[i][0] = dp[i - 1][0];\n",
    "            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);\n",
    "            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);\n",
    "            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);\n",
    "            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);\n",
    "\n",
    "        print(dp)\n",
    "\n",
    "        return dp[numslen - 1][4] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\"\"\"\n",
    "状态表示\n",
    "第几天 x 交易了几次 x [未买入、买入、持有、卖出]\n",
    "\n",
    "i天，第一次交易，未买入 = i-1天，第一次交易，未买入\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = np.zeros((n, 2, 4), dtype='int')\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i] = -1e11\n",
    "            if i == 0:\n",
    "                dp[0][0][0] = 0\n",
    "                dp[0][0][1] = -prices[0]\n",
    "            else:\n",
    "                dp[i][0][0] = dp[i-1][0][0]\n",
    "                dp[i][0][1] = dp[i-1][0][0] - prices[i]\n",
    "                dp[i][0][2] = max(dp[i-1][0][1], dp[i-1][0][2])\n",
    "                dp[i][0][3] = max(dp[i-1][0][1], dp[i-1][0][2]) + prices[i]\n",
    "\n",
    "                dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][3])\n",
    "                dp[i][1][1] = max(dp[i-1][1][0], dp[i-1][0][3]) - prices[i]\n",
    "                dp[i][1][2] = max(dp[i-1][1][1], dp[i-1][1][2])\n",
    "                dp[i][1][3] = max(dp[i-1][1][1], dp[i-1][1][2]) + prices[i]\n",
    "\n",
    "        return int(np.max(dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\"\"\"\n",
    "状态表示\n",
    "第几天 x 交易了几次 x [未买入、买入、持有、卖出]\n",
    "\n",
    "i天，第一次交易，未买入 = i-1天，第一次交易，未买入\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = np.zeros((n, 2, 4), dtype='int')\n",
    "\n",
    "        v = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = -1e11\n",
    "            if i == 0:\n",
    "                dp[0][0][0] = 0\n",
    "                dp[0][0][1] = -prices[0]\n",
    "            else:\n",
    "                dp[i][0][0] = dp[i-1][0][0]\n",
    "                dp[i][0][1] = dp[i-1][0][0] - prices[i]\n",
    "                dp[i][0][2] = max(dp[i-1][0][1], dp[i-1][0][2])\n",
    "                dp[i][0][3] = max(dp[i-1][0][1], dp[i-1][0][2]) + prices[i]\n",
    "\n",
    "                dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][3])\n",
    "                dp[i][1][1] = max(dp[i-1][1][0], dp[i-1][0][3]) - prices[i]\n",
    "                dp[i][1][2] = max(dp[i-1][1][1], dp[i-1][1][2])\n",
    "                dp[i][1][3] = max(dp[i-1][1][1], dp[i-1][1][2]) + prices[i]\n",
    "\n",
    "            v = max(v, np.max(dp[i]))\n",
    "        return int(v)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        K = 2\n",
    "        # 前i天经过k次买/卖后，手头最大收益\n",
    "        bought = [[float(\"-inf\") for k in range(K + 1)] for i in range(len(prices) + 1)]\n",
    "        sold = [[0 for k in range(K + 1)] for i in range(len(prices) + 1)]\n",
    "\n",
    "        for i in range(1, len(prices) + 1):\n",
    "            for k in range(1, K + 1):\n",
    "                # 第i天经过k次买卖\n",
    "                bought[i][k] = max(\n",
    "                    # 前一天经过k-1次完整买卖，手头不持有，今天买入\n",
    "                    sold[i - 1][k - 1] - prices[i - 1],\n",
    "                    # 前一天，经k次买入，手头持有\n",
    "                    bought[i - 1][k],\n",
    "                )\n",
    "                # 第i天，k次买入\n",
    "                sold[i][k] = max(\n",
    "                    # 前一天，经k次买入，手头持有，今天卖出\n",
    "                    bought[i - 1][k] + prices[i - 1],\n",
    "                    # 前一天，经k次完整买卖，手头不持有\n",
    "                    sold[i - 1][k],\n",
    "                )\n",
    "        \n",
    "        return sold[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        l=len(prices)\n",
    "        # 0：持0  1：持1\n",
    "        # 0：不持0 1： 不持1 2：不持2  \n",
    "        dp=[[[0,0],[0,0,0]] for i in range(l)]\n",
    "        dp[0]=[[-prices[0],-prices[0]],[0,0,0]]\n",
    "        for i in range(1,l):\n",
    "            # 持0  不持0买 持0 \n",
    "            dp[i][0][0]=max(dp[i-1][1][0]-prices[i],dp[i-1][0][0])\n",
    "            # 持1 不持1买 持1 持0卖买\n",
    "            dp[i][0][1]=max(dp[i-1][1][1]-prices[i],dp[i-1][0][1])\n",
    "            # 不持0 不持0\n",
    "            dp[i][1][0]=dp[i-1][1][0]\n",
    "            # 不持1 不持1 持0卖\n",
    "            dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][0]+prices[i])\n",
    "            # 不持2 不持2 持1卖\n",
    "            dp[i][1][2]=max(dp[i-1][1][2],dp[i-1][0][1]+prices[i])\n",
    "\n",
    "        return max(dp[l-1][1][1], dp[l-1][1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #dp = [[[0] * 2] * 2] * len(prices)\n",
    "        dp = [[[0] * 2 for _ in range(2)] for _ in range(len(prices))]\n",
    "\n",
    "        \n",
    "        \n",
    "        for i in range(len(prices)):\n",
    "            if i == 0:\n",
    "                dp[0][0][1] = -prices[0]\n",
    "                dp[0][1][1] = -prices[0]\n",
    "            else:\n",
    "                dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][0][1] + prices[i])\n",
    "                dp[i][0][1] = max(dp[i - 1][0][1], 0 - prices[i])\n",
    "                dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])\n",
    "                dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])\n",
    "\n",
    "        \n",
    "        return dp[-1][1][0]\n",
    "                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[0] * 3 for _ in range(2)] for _ in range(n)]\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][0][1] = 0\n",
    "        dp[0][0][2] = 0\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        dp[0][1][1] = -prices[0]\n",
    "        dp[0][1][2] = -9999999\n",
    "        for i in range(1, n):\n",
    "                dp[i][0][2] = 0\n",
    "                dp[i][1][2] = -9999999\n",
    "        for i in range(1, n):\n",
    "            k = 1\n",
    "            while k >= 0:\n",
    "                dp[i][0][k] = max(dp[i-1][1][k] + prices[i], dp[i-1][0][k])\n",
    "                dp[i][1][k] = max(dp[i-1][0][k+1] - prices[i], dp[i-1][1][k])\n",
    "                k -= 1\n",
    "        return max(dp[n-1][0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #复制\n",
    "        n=len(prices)\n",
    "        dp=[[[0,0,0],[0,0,0]] for _ in range(n)]\n",
    "        dp[0][1][0]=-prices[0]\n",
    "        dp[0][0][1]=-inf\n",
    "        dp[0][0][2]=-inf\n",
    "        dp[0][1][1]=-inf\n",
    "        dp[0][1][2]=-inf\n",
    "        for i in range(1,n):\n",
    "            #未持股，未卖出过，说明从未进行过买卖\n",
    "            dp[i][0][0]=0\n",
    "            #未持股，卖出过1次，可能是今天卖的，可能是之前卖的\n",
    "            dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])\n",
    "            #未持股，卖出过2次，可能是今天卖的，可能是之前卖的\n",
    "            dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])\n",
    "            #持股，未卖出过，可能是今天买的，可能是之前买的\n",
    "            dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])\n",
    "            #持股，卖出过1次，可能是今天买的，可能是之前买的\n",
    "            dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])\n",
    "            #持股，卖出过2次，不可能\n",
    "            dp[i][1][2]=-inf\n",
    "        return max(dp[n-1][0][1],dp[n-1][0][2],0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#垃圾\n",
    "    # def maxProfit(self, prices: List[int]) -> int:\n",
    "    #     low1=high1=prices[0]\n",
    "    #     low2=high2=prices[len(prices)-1]\n",
    "    #     profit1=[0]*len(prices)\n",
    "    #     profit2=[0]*len(prices)\n",
    "    #     profit=profit3=profit4=0\n",
    "    #     for i in range(0,len(prices)):\n",
    "    #         if(prices[i]<low1):\n",
    "    #             high1=low1=prices[i]\n",
    "    #         if(prices[i]>high1):\n",
    "    #             high1=prices[i]\n",
    "    #         profit3=max(profit3,high1-low1)\n",
    "    #         profit1[i]=profit3\n",
    "    #         if(prices[len(prices)-1-i]<low2):\n",
    "    #             low2=prices[len(prices)-1-i]\n",
    "    #         if(prices[len(prices)-1-i]>high2):\n",
    "    #             high2=low2=prices[len(prices)-1-i]\n",
    "    #         profit4=max(profit4,high2-low2)\n",
    "    #         profit2[len(prices)-1-i]=profit4\n",
    "    #     for k in range(0,len(prices)):\n",
    "    #         profit = max(profit,profit1[k]+profit2[k])\n",
    "    #         print(profit)\n",
    "    #     return profit\n",
    "    # def maxProfit(self, prices: List[int]) -> int:\n",
    "    #     n = len(prices)\n",
    "    #     buy1 = buy2 = -prices[0]\n",
    "    #     sell1 = sell2 = 0\n",
    "    #     for i in range(1, n):\n",
    "    #         buy1 = max(buy1, -prices[i])\n",
    "    #         sell1 = max(sell1, buy1 + prices[i])\n",
    "    #         buy2 = max(buy2, sell1 - prices[i])\n",
    "    #         sell2 = max(sell2, buy2 + prices[i])\n",
    "    #     return sell2\n",
    "\n",
    "\n",
    "\n",
    "       #超时！！！\n",
    "        # n = len(prices)\n",
    "        # profit = max(prices[-1] - prices[0], 0)\n",
    "        # for j in range(1, n):  # 调整循环范围\n",
    "        #     # 第一次交易的最大利润\n",
    "        #     profit1 = 0\n",
    "        #     min_price1 = prices[0]\n",
    "        #     for i in range(j):\n",
    "        #         min_price1 = min(min_price1, prices[i])\n",
    "        #         profit1 = max(profit1, prices[i] - min_price1)\n",
    "\n",
    "        #     # 第二次交易的最大利润\n",
    "        #     profit2 = 0\n",
    "        #     max_price2 = prices[-1]\n",
    "        #     for i in range(n - 1, j - 1, -1):  # 调整循环范围\n",
    "        #         max_price2 = max(max_price2, prices[i])\n",
    "        #         profit2 = max(profit2, max_price2 - prices[i])\n",
    "\n",
    "        #     # 总的最大利润\n",
    "        #     profit = max(profit, profit1 + profit2)\n",
    "\n",
    "        # return profit\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[天][是否持有][已经完成几次]\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        dp = [[[0, 0, 0] for _ in range(2)] for _ in range(len(prices) + 1)]\n",
    "        dp[0][0][1] = -inf\n",
    "        dp[0][0][2] = -inf\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        dp[0][1][1] = -inf\n",
    "        dp[0][1][2] = -inf\n",
    "        for i in range(1, len(prices) + 1):\n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i-1])\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1] + prices[i-1])\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i-1])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1],  dp[i-1][0][1] - prices[i-1])\n",
    "            dp[i][1][2] = -inf\n",
    "        return max(dp[i][0][2], dp[i][0][1], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        n = len(prices)\n",
    "        max_trade = 2\n",
    "        dp = [[[0]*2 for _ in range(max_trade+1)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(max_trade, 0, -1):\n",
    "                if i == 0:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])\n",
    "                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])\n",
    "\n",
    "        return dp[n-1][max_trade][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        # @cache\n",
    "        # def dfs(i,hold,k):\n",
    "        #     if k < 0:\n",
    "        #         return -inf\n",
    "        #     if i < 0:\n",
    "        #         return 0 if not hold else -inf\n",
    "        #     if hold:\n",
    "        #         return max(dfs(i-1,True,k),dfs(i-1,False,k)-prices[i])\n",
    "        #     return max(dfs(i-1,False,k),dfs(i-1,True,k-1)+prices[i])\n",
    "        # return dfs(n-1,False,2)\n",
    "        f = [[[-inf] * 4 for _ in range(2)] for _ in range(n+1)]\n",
    "        for i in range(1,4):\n",
    "            f[0][0][i] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,4):\n",
    "                f[i][0][j] = max(f[i-1][0][j],f[i-1][1][j-1]+prices[i-1])\n",
    "                f[i][1][j] = max(f[i-1][1][j],f[i-1][0][j]-prices[i-1])\n",
    "\n",
    "        return f[n][0][3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        k = 2\n",
    "        n = len(prices)\n",
    "        ans = [[[-float('inf')]*2 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for j in range(k+1):\n",
    "            ans[0][j][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ans[i][0] = ans[i-1][0]\n",
    "            for j in range(1, k + 1):\n",
    "                ans[i][j][0] = max(ans[i-1][j][1] + prices[i-1], ans[i-1][j][0])\n",
    "                ans[i][j][1] = max(ans[i-1][j-1][0] - prices[i-1], ans[i-1][j][1])\n",
    "        return ans[n][k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        N = len(prices)\n",
    "        # 状态定义 dp[i][j][k]代表在第i天，被允许完成j次交易时，持有或者不持有的最大利润。k=0代表不持有，k=1代表持有\n",
    "        dp = [[[0 for k in range(2)] for j in range(3)] for i in range(N)]\n",
    "\n",
    "        for i in range(N):\n",
    "            for j in range(1, 3):\n",
    "                # badcase\n",
    "                if i - 1 == -1:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])\n",
    "                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])\n",
    "\n",
    "        return dp[N-1][2][0]\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        max_k = 2\n",
    "        dp = [[[0] * 2 for _ in range(max_k + 2)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for k in range(max_k, 0, -1):\n",
    "                if i - 1 == -1:\n",
    "                    dp[i][k][0] = 0\n",
    "                    dp[i][k][1] = -prices[i]\n",
    "                    continue\n",
    "                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])\n",
    "                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])\n",
    "        return dp[n-1][max_k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        买卖股票所获得的最大的利润\n",
    "        Args:\n",
    "            prices (list[int]): 每天的股票价格\n",
    "        returns (int): 最终所能够获得的最大利润\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if prices == None or len(prices) <= 1:\n",
    "            return 0 \n",
    "        \n",
    "        n = len(prices)\n",
    "        \n",
    "        #dp的定义, dp[i][j][k]表示[...i]天的情况下, 在拥有股票(1表示拥有股票, 0表示不拥有股票), 已经发生k次交易的情况下, 所能够获得的最大的利润\n",
    "        dp = [[[-float('inf') for _ in range(3)] for _ in range(2)] for _ in range(n)]\n",
    "\n",
    "        #dp的初始化\n",
    "        dp[0][0][0] = 0             #在第0天不进行操作\n",
    "        dp[0][1][0] = -prices[0]    #在第0天买入股票\n",
    "        \n",
    "        #dp的遍历, dp的状态转移\n",
    "        for i in range(1, n):\n",
    "            #1.第i天持有股票\n",
    "                #case1.1 未进行过交易(卖出操作), 可能的情况为(前一天拥有股票且未进行过交易; 前一天不拥有股票且没有进行过交易, 今天买入股票)\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i])\n",
    "                \n",
    "                #case1.2 进行了一次交易, 可能存在的情况为(前一天拥有股票且进行过一次交易今天不操作； 前一天不拥有股票且进行过一次交易， 今天买入股票)\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1] - prices[i])\n",
    "                \n",
    "                #case1.3 进行了两次交易, 此种方法必然不是最大值\n",
    "            dp[i][1][2] = -float(\"inf\")\n",
    "            \n",
    "            #2.第i天不持有股票\n",
    "                #case2.1 没有进行过交易\n",
    "            dp[i][0][0] = dp[i-1][0][0] \n",
    "                \n",
    "                #case2.2 进行过一次交易\n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i])\n",
    "                \n",
    "                #case2.3 进行过两次交易\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1] + prices[i])\n",
    "        \n",
    "        ans = 0\n",
    "        #遍历dp, 找寻最大利润\n",
    "        for i in range(n):\n",
    "            for j in range(2):\n",
    "                for k in range(3):\n",
    "                    if dp[i][j][k] > ans:\n",
    "                        ans = dp[i][j][k]\n",
    "        \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        import numpy as np\n",
    "        dp = [[[-1e10 for _ in range(3)] for _ in range(2)] for _ in range(len(prices))]\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0][0] = dp[i-1][0][0]\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i])\n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1] - prices[i])\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1] + prices[i])\n",
    "        return max(dp[-1][0][0], dp[-1][0][1], dp[-1][0][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[0] * 2 for _ in range(4)] for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            for j in range(4):\n",
    "                for k in range(2):\n",
    "                    if i == 0:\n",
    "                        dp[i][j][k] = -inf if k == 1 else 0\n",
    "                    elif j == 0:\n",
    "                        dp[i][j][k] = -inf\n",
    "                    else:\n",
    "                        if k:\n",
    "                            dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i - 1])\n",
    "                        else:\n",
    "                            dp[i][j][0] = max(dp[i - 1][j - 1][1] + prices[i - 1], dp[i - 1][j][0])\n",
    "        return dp[n][3][0]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        \n",
    "        # 动态规划\n",
    "        # dp = [[[-inf] * ]]\n",
    "        # 递归\n",
    "        # @cache\n",
    "        # def dfs(i, j, hold):\n",
    "        #     if j < 0:\n",
    "        #         return -inf\n",
    "        #     if i < 0:\n",
    "        #         return -inf if hold else 0\n",
    "        #     if hold:\n",
    "        #         return max(dfs(i - 1, j, True), dfs(i - 1, j, False) - prices[i])\n",
    "        #     return max(dfs(i - 1, j, False), dfs(i - 1, j - 1, True) + prices[i])\n",
    "        # return dfs(len(prices) - 1, 2, False)\n",
    "\n",
    "        # 二刷 2023 11 21\n",
    "        # 法一 递归\n",
    "        # @cache\n",
    "        # def dfs(i, j, hold):\n",
    "        #     if j < 0:\n",
    "        #         return -inf\n",
    "        #     if i < 0:\n",
    "        #         return -inf if hold else 0\n",
    "        #     if hold:\n",
    "        #         return max(dfs(i-1, j, True), dfs(i-1, j-1, False) - prices[i])\n",
    "        #     return max(dfs(i-1, j, False), dfs(i-1, j, True) + prices[i])\n",
    "        # return dfs(len(prices) - 1, 2, False)\n",
    "\n",
    "        # 法二 动态规划\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf] * 2 for _ in range(4)] for _ in range(n+1)]\n",
    "        for j in range(1, 4):\n",
    "            dp[0][j][0] = 0\n",
    "        for i, p in enumerate(prices):\n",
    "            for j in range(1, 4):\n",
    "                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j][1] + p)\n",
    "                dp[i+1][j][1] = max(dp[i][j][1], dp[i][j-1][0] - p)\n",
    "        return dp[n][3][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = np.zeros((len(prices), 3, 2), dtype = int).tolist()\n",
    "        for i in range(3):\n",
    "            dp[0][i][1] = -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1]+prices[i])\n",
    "            dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0]-prices[i])\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1]+prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0]-prices[i])\n",
    "        return dp[len(prices)-1][2][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        k=2\n",
    "        n=len(prices)\n",
    "        dp=[[[-float(\"inf\") for _ in range(2)]for _ in range(k+1)]for _ in range(n)]\n",
    "        for i in range(k+1):\n",
    "            dp[0][i][0]=0\n",
    "            dp[0][i][1]=-prices[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(k+1):\n",
    "                if j==0:\n",
    "                    dp[i][j][0]=0\n",
    "                if j!=0:\n",
    "                    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])\n",
    "                dp[i][j][1]=max(dp[i-1][j][1],dp[i][j][0]-prices[i])\n",
    "        #print(dp)\n",
    "        return dp[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        import numpy\n",
    "        if not prices:\n",
    "            return 0\n",
    "        duration = len(prices)\n",
    "    # 结束时的最高利润=[天数][是否持有股票][卖出次数]\n",
    "        profit = [[[0, 0, 0], [0, 0, 0]] for i in range(0, duration)]\n",
    "    # 第一天休息\n",
    "        profit[0][0][0] = 0\n",
    "    # 第一天买入\n",
    "        profit[0][1][0] = -prices[0]\n",
    "    # 第一天不可能已经有卖出\n",
    "        profit[0][0][1] = float('-inf')\n",
    "        profit[0][0][2] = float('-inf')\n",
    "    # 第一天不可能已经卖出\n",
    "        profit[0][1][1] = float('-inf')\n",
    "        profit[0][1][2] = float('-inf')\n",
    "        for i in range(1, duration):\n",
    "        # 未持股，未卖出过，说明从未进行过买卖\n",
    "            profit[i][0][0] = 0\n",
    "        # 未持股，卖出过1次，可能是今天卖的，可能是之前卖的\n",
    "            profit[i][0][1] = max(profit[i - 1][1][0] + prices[i], profit[i - 1][0][1])\n",
    "        # 未持股，卖出过2次，可能是今天卖的，可能是之前卖的\n",
    "            profit[i][0][2] = max(profit[i - 1][1][1] + prices[i], profit[i - 1][0][2])\n",
    "        # 持股，未卖出过，可能是今天买的，可能是之前买的\n",
    "            profit[i][1][0] = max(profit[i - 1][0][0] - prices[i], profit[i - 1][1][0])\n",
    "        # 持股，卖出过1次，可能是今天买的，可能是之前买的\n",
    "            profit[i][1][1] = max(profit[i - 1][0][1] - prices[i], profit[i - 1][1][1])\n",
    "        # 持股，卖出过2次，不可能\n",
    "            profit[i][1][2] = float('-inf')\n",
    "        return max(profit[duration - 1][0][1], profit[duration - 1][0][2], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        import numpy as np\n",
    "\n",
    "        #init\n",
    "        dp = [[[0 for i in range(2)] for j in range(3)] for k in range(len(prices))]\n",
    "        for i in range(3):\n",
    "            for j in range(2):\n",
    "                dp[0][i][j] = -np.inf\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][0][1] = - prices[0]\n",
    "\n",
    "\n",
    "        #transition functionm\n",
    "        for i in range(1,len(prices)):\n",
    "            for j in range(3):\n",
    "                dp[i][j][1] = max(dp[i - 1][j][1], dp[i-1][j][0] - prices[i])\n",
    "                if j>=1:\n",
    "                    dp[i][j][0] = max(dp[i - 1][j][0], dp[i-1][j - 1][1] + prices[i])\n",
    "                else:\n",
    "                    dp[i][j][0] = 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            if dp[-1][i][0]>res:\n",
    "                res = dp[-1][i][0]\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # prices = [7,6,4,3,1] \n",
    "        n = len(prices)\n",
    "        K = 2*2\n",
    "        dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = -float('inf')\n",
    "            for j in range(K, 0, -1):\n",
    "                if i-1 == -1:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                    continue\n",
    "\n",
    "                # 1.昨天未持有，今天rest 2.昨天持有，今天卖了\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] + prices[i])\n",
    "\n",
    "                # 1.昨天持有，今天rest 2.昨天未持有，今天买了\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])\n",
    "                \n",
    "        return dp[n-1][K][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [ [ [ 0 for i in range(2) ] for j in range(5) ] for k in range(len(prices)+5) ]\n",
    "        INF = 1e9+7\n",
    "        dp[0][0][1] = -prices[0]\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][1][1] = -INF\n",
    "        dp[0][1][0] = -INF\n",
    "        dp[0][2][1] = -INF\n",
    "        dp[0][2][0] = -INF\n",
    "        ans = -1\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][1][1] + prices[i])\n",
    "            dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][2][0] - prices[i])\n",
    "\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][1]+prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][1][0] - prices[i])\n",
    "            dp[i][0][0] = dp[i-1][0][0]\n",
    "            dp[i][0][1] = max( dp[i-1][0][1], dp[i-1][0][0] - prices[i] )\n",
    "\n",
    "        ans = max(ans, dp[len(prices)-1][2][0])\n",
    "        ans = max(ans, dp[len(prices)-1][1][0])\n",
    "        ans = max(ans, dp[len(prices)-1][0][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        k = 2\n",
    "\n",
    "        f = [[[-inf, -inf] for _ in range(k + 2)] for _ in range(n + 1)]\n",
    "\n",
    "        for j in range(1, k + 2):\n",
    "            f[0][j][0] = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 2):\n",
    "                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - prices[i - 1])\n",
    "                f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][1] + prices[i - 1])\n",
    "\n",
    "        return f[n][k + 1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "    \n",
    "    ## 定义dp[i][k][0]表示第i天且进行了k（k=0，1，2）次交易（不持有股票）的最大收益\n",
    "    ## 定义dp[i][k][1]表示第i天且进行了k次交易（持有股票）的最大收益\n",
    "    ## dp[i][k][1] = max(dp[i-1][k][0]-prices[i],dp[i-1][k-1][1])\n",
    "    ## dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i])\n",
    "    ## 初始条件： dp[i][k][0] = 0 dp[i][k][1] = -prices[0] k= 0 1 2\n",
    "\n",
    "        length = len(prices)\n",
    "        if length<2:\n",
    "            return 0\n",
    "        dp = np.zeros([length,3,2]).tolist()\n",
    "\n",
    "        for k in range(3):\n",
    "            dp[0][k][0] = 0\n",
    "            dp[0][k][1] = -prices[0]\n",
    "\n",
    "        for i in range(1,length):\n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])\n",
    "            for k in range(1,3):\n",
    "                dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i])\n",
    "                dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k][0]-prices[i])\n",
    "\n",
    "        return dp[length-1][2][0]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sys import maxsize\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        profit[day][k][hold_stock]\n",
    "        0 <= day <= len(prices)-1\n",
    "        k: the max number of transaction so far. 0 <= k <= 2\n",
    "        hold_stock: 0 False, 1 True\n",
    "        \"\"\"\n",
    "        days = len(prices)\n",
    "        K = 2\n",
    "        profit = [[[-maxsize-1 for _ in range(2)] for _ in range(K+1)] for _ in range(days)]\n",
    "\n",
    "        # base cases day = 0\n",
    "        for k in range(K+1):\n",
    "            profit[0][k][0] = 0\n",
    "            profit[0][k][1] = -prices[0]\n",
    "        # base cases k = 0\n",
    "        for day in range(days):\n",
    "            profit[day][0][0] = 0\n",
    "\n",
    "        for day in range(1, days):\n",
    "            for k in range(1, K+1):\n",
    "                profit[day][k][0] = max(profit[day-1][k][0], profit[day-1][k][1] + prices[day])\n",
    "                profit[day][k][1] = max(profit[day-1][k][1], profit[day-1][k-1][0] - prices[day])\n",
    "        return profit[days-1][K][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        vals = [[[-math.inf for x in range(2)] for y in range(3)] for z in range(len(prices))]\n",
    "\n",
    "        vals[0][2][0] = 0\n",
    "        vals[0][1][1] = -prices[0]\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "\n",
    "            vals[i][2][0] = vals[i-1][2][0]\n",
    "\n",
    "            for j in range(2):\n",
    "                vals[i][j][0] = max(vals[i-1][j][1] + prices[i], vals[i-1][j][0]) # if no stock today, either sell or stay same\n",
    "                vals[i][j][1] = max(vals[i-1][j+1][0] - prices[i], vals[i-1][j][1]) # if have stock today, either buy or stay same\n",
    "            \n",
    "        print(vals[len(prices)-1])\n",
    "        print([vals[len(prices)-1][i][0] for i in range(2)])\n",
    " \n",
    "        return max([vals[len(prices)-1][i][0] for i in range(3)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # 记忆化搜索\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(day, j, hold):\n",
    "        #     if j < 0:\n",
    "        #          return -inf\n",
    "        #     if day == -1:\n",
    "        #         return -inf if hold else 0\n",
    "        #     if hold:\n",
    "        #         return max(dfs(day-1, j, True), dfs(day-1, j-1, False)-prices[day])\n",
    "        #     else:\n",
    "        #         return max(dfs(day-1, j, False), dfs(day-1, j, True)+prices[day])\n",
    "        # n = len(prices)\n",
    "        # return dfs(n-1, 2, False)\n",
    "        # 递推\n",
    "        k = 2\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf for _ in range(2)] for _ in range(k+2)] for _ in range(n+1)]\n",
    "        for i in range(k+2):\n",
    "            dp[0][i][0] = 0\n",
    "            dp[0][i][1] = -inf\n",
    "        for i in range(n):\n",
    "            for j in range(1, k+2):\n",
    "                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j-1][1]+prices[i])\n",
    "                dp[i+1][j][1] = max(dp[i][j][1], dp[i][j][0]-prices[i])\n",
    "        return dp[n][k+1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        index = {(i,j):0 for i in range(n) for j in range(4)}\n",
    "        index[0,0] = -prices[0]\n",
    "        index[0,2] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            index[i,0] = max(index[i-1,0], - prices[i])\n",
    "            index[i,1] = max(index[i-1,1], index[i-1, 0] + prices[i])\n",
    "            index[i,2] = max(index[i-1,2], index[i-1, 1] - prices[i])\n",
    "            index[i,3] = max(index[i-1,3], index[i-1, 2] + prices[i])\n",
    "        return index[n-1,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        dp[('no', 0, 0)] = float('-inf')\n",
    "        dp[('no', 0, 1)] = float('-inf')\n",
    "        dp[('no', 0, 2)] = 0\n",
    "        dp[('yes', 0, 1)] = -prices[0]\n",
    "        dp[('yes', 0, 0)] = float('-inf')\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[('yes', i, 1)] = max(dp[('yes', i - 1, 1)], dp[('no', i - 1, 2)] - prices[i])\n",
    "            dp[('yes', i, 0)] = max(dp[('yes', i - 1, 0)], dp[('no', i - 1, 1)] - prices[i])\n",
    "\n",
    "            dp[('no', i, 2)] = dp[('no', i - 1, 2)]\n",
    "            dp[('no', i, 1)] = max(dp[('no', i - 1, 1)], dp[('yes', i - 1, 1)] + prices[i])\n",
    "            dp[('no', i, 0)] = max(dp[('no', i - 1, 0)], dp[('yes', i - 1, 0)] + prices[i])\n",
    "        \n",
    "        return max(max(dp[('no', len(prices) - 1, 0)], dp[('no', len(prices) - 1, 1)]), dp[('no', len(prices) - 1, 2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        a = self.f2(prices)\n",
    "        self.f1(prices)\n",
    "        return a\n",
    "\n",
    "    def f2(self, prices):\n",
    "        dp = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(len(prices)+1)]\n",
    "        dp[0][0][1] = -inf\n",
    "        dp[0][1][1] = -inf\n",
    "        dp[0][2][1] = -inf\n",
    "        for i in range(1, len(prices)+1):\n",
    "            for j in range(1, 3):\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1])\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1])\n",
    "        import numpy as np\n",
    "        print(np.array(dp))\n",
    "        return dp[-1][-1][0]\n",
    "\n",
    "    def f1(self, prices):\n",
    "        l=len(prices)\n",
    "        import numpy as np\n",
    "        dp=np.zeros([l+1,3,2])\n",
    "        dp[0,:,1]=-np.inf\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(1,3):\n",
    "                dp[i,j,0] = max(dp[i-1,j,0],dp[i-1,j,1]+prices[i-1])\n",
    "                dp[i,j,1] = max(dp[i-1,j,1],dp[i-1,j-1,0]-prices[i-1])\n",
    "        print(dp)\n",
    "        return int(dp[-1,-1,0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dic = {}\n",
    "        dic[(0,0)] = 0\n",
    "        dic[(0,1)] = -prices[0]\n",
    "        dic[(0,2)] = 0\n",
    "        dic[(0,3)] = -prices[0]\n",
    "        dic[(0,4)] = 0\n",
    "        max_val = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            cur_p = prices[i]\n",
    "            dic[(i,0)] = 0\n",
    "            dic[(i,1)] = max(dic[(i-1,1)], -cur_p)\n",
    "            dic[(i,2)] = max(cur_p+dic[(i-1,1)], dic[(i-1,2)])\n",
    "            max_val = max(max_val, dic[(i,2)])\n",
    "            dic[(i,3)] = max(dic[(i-1,2)]-cur_p, dic[(i-1,3)])\n",
    "            dic[(i,4)] = max(dic[(i-1,4)],cur_p + dic[(i-1,3)])\n",
    "            max_val = max(max_val, dic[(i,4)])\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        dp[(0,0,0)] = 0 # I天买入k次当前不持有 利润\n",
    "        dp[(0,1,1)] = -prices[0]\n",
    "        dp[(0,1,0)] = 0\n",
    "        dp[(0,2,1)] = -prices[0]\n",
    "        dp[(0,2,0)] = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[(i,0,0)] = dp[(i-1,0,0)]\n",
    "            dp[(i,1,0)] = max(dp[(i-1,1,0)], dp[(i-1,1,1)] + prices[i])\n",
    "            dp[(i,2,0)] = max(dp[(i-1,2,0)], dp[(i-1,2,1)] + prices[i])\n",
    "\n",
    "            dp[(i,1,1)] = max(dp[(i-1,1,1)], dp[(i-1,0,0)] - prices[i])\n",
    "            dp[(i,2,1)] = max(dp[(i-1,2,1)], dp[(i-1,1,0)]-prices[i], dp[(i-1,1,1)])\n",
    "        return max(0, dp[(len(prices)-1,0,0)], dp[(len(prices)-1,1,0)], dp[(len(prices)-1,2,0)], dp[(len(prices)-1,1,1)], dp[(len(prices)-1,2,1)] ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        k = 2\n",
    "        k = min(k, n//2)\n",
    "        ans = 0\n",
    "        dp = defaultdict(lambda: float('-inf'))\n",
    "        \n",
    "        # iteration \n",
    "        dp[(0, 0, \"buy\")] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            dp[(i, 0, \"buy\")] = max(dp[(i-1, 0, \"buy\")], -prices[i])\n",
    "\n",
    "        # bound \n",
    "        for i in range(1, len(prices)):\n",
    "            for j in range(1, k+1):    \n",
    "                dp[(i, j, \"sell\")] = max(dp[(i-1, j-1,  \"buy\")] + prices[i], dp[(i-1, j, \"sell\")])    \n",
    "                dp[(i, j,  \"buy\")] = max(dp[(i-1,   j, \"sell\")] - prices[i], dp[(i-1, j, \"buy\")])    \n",
    "                ans = max(ans, dp[(i, j, \"sell\")])\n",
    "                 \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        max_k = 2\n",
    "        for i in range(len(prices)):\n",
    "            dp[i] = {}\n",
    "            for k in range (max_k, 0, -1):\n",
    "                dp[i][k] = {}\n",
    "                if i - 1 == -1:\n",
    "                    dp[i][k][0] = 0\n",
    "                    dp[i][k][1] = -prices[i]\n",
    "                    continue\n",
    "                \n",
    "                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])\n",
    "                \n",
    "                if k - 1 == 0:\n",
    "                    dp[i][k][1] = max(dp[i - 1][k][1],  - prices[i])\n",
    "                else:\n",
    "                    dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])\n",
    "        \n",
    "        return dp[len(prices) - 1][max_k][0]\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf for k in range(2)] for j in range(2+1)] for i in range(n+1)]\n",
    "        #[i,j,k]->i表示第几天，j表示至多交易了几次(0次，1次，2次)，k表示是否含股票(0不含，1含)\n",
    "        dp = np.array(dp)\n",
    "        #print(np.array(dp).shape)   #(9,3,2)\n",
    "        #初始化 \n",
    "        for i in range(n+1):   \n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = -inf\n",
    "        for j in range(2+1):\n",
    "            dp[0][j][0] = 0\n",
    "            dp[0][j][1] = -prices[0]\n",
    "        #循环-把买入当成一次交易\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1,3):\n",
    "                #不含且最多交易了j次  =max(昨天不含且交易了j次-不操作，昨天含且交易了j次-卖出)\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i-1])\n",
    "                #  含且最多交易了j次  =max(昨天含且交易了j次-不操作，昨天不含且交易了j-1-买入)\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i-1])\n",
    "        # print(dp)\n",
    "\n",
    "        return int(max(dp[-1][-1][0], dp[-1][-1][1]))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        trades = 2\n",
    "        dp = [[{'cash': 0, 'stock': -float('inf')} for kth_trade in range(trades + 1)] for day in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for k in range(1, trades + 1):\n",
    "                dp[i][k]['cash'] = max(dp[i - 1][k]['cash'], dp[i - 1][k]['stock'] + prices[i - 1])\n",
    "                dp[i][k]['stock'] = max(dp[i - 1][k]['stock'], dp[i - 1][k - 1]['cash'] - prices[i - 1])\n",
    "        return max([dp[-1][k]['cash'] for k in range(1, trades + 1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        count = 2\n",
    "        dp = dict()\n",
    "        for i in range(n):\n",
    "            dp[(i,0,0)] = 0\n",
    "            dp[(i,1,0)] = float(\"-inf\")\n",
    "        for k in range(1, count+1):\n",
    "            dp[(0,0,k)] = 0\n",
    "            dp[(0,1,k)] = -prices[0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for k in range(1, count+1):\n",
    "                dp[(i,0,k)] = max(dp.get((i-1,0,k), 0), dp.get((i-1,1,k),0)+prices[i])\n",
    "                dp[(i,1,k)] = max(dp.get((i-1,1,k), 0), dp.get((i-1,0,k-1),0)-prices[i])\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for k in range(count+1):\n",
    "                res = max(res, dp.get((i,0,k), 0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # 状态与选择\n",
    "        # 状态：赚到的钱\n",
    "        # 选择：时间，交易次数，是否持有\n",
    "        dp = {}\n",
    "\n",
    "        # 遍历某个变量，考虑另一个变量为极端值的情况\n",
    "        for i in range(-1, len(prices)):\n",
    "            dp[(i, 0, 0)] = 0\n",
    "            dp[(i, 0, 1)] = -sys.maxsize\n",
    "        \n",
    "        for k in range(3):\n",
    "            dp[(-1, k, 0)] = 0\n",
    "            dp[(-1, k, 1)] = -sys.maxsize\n",
    "\n",
    "        \n",
    "        for i in range(len(prices)):\n",
    "            for k in [1, 2]:\n",
    "                dp[(i, k, 0)] = max(dp[(i-1, k, 0)], dp[(i-1, k, 1)]+prices[i])\n",
    "                dp[(i, k, 1)] = max(dp[(i-1, k, 1)], dp[(i-1, k-1, 0)]-prices[i])\n",
    "\n",
    "        return dp[(len(prices)-1, 2, 0)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        length = len(prices)\n",
    "\n",
    "        def dfs(depth: int, count: int, is_has_stock: bool):\n",
    "            if depth == length or count == 2:\n",
    "                return 0\n",
    "            profit_sell, profit_buy, profit_nothing = 0, 0, 0\n",
    "            profit_nothing = dfs(depth+1, count, is_has_stock)\n",
    "            if is_has_stock:\n",
    "                profit_sell = dfs(depth+1, count+1, False) + prices[depth]\n",
    "            else:\n",
    "                profit_buy = dfs(depth+1, count, True) - prices[depth]\n",
    "            return max(profit_sell, profit_buy, profit_nothing)\n",
    "        return dfs(0, 0, False)\n",
    "\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        length = len(prices)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(depth: int, count: int, is_has_stock: bool):\n",
    "            if depth == length or count == 2:\n",
    "                return 0\n",
    "            profit_sell, profit_buy, profit_nothing = 0, 0, 0\n",
    "            profit_nothing = dfs(depth+1, count, is_has_stock)\n",
    "            if is_has_stock:\n",
    "                profit_sell = dfs(depth+1, count+1, False) + prices[depth]\n",
    "            else:\n",
    "                profit_buy = dfs(depth+1, count, True) - prices[depth]\n",
    "            return max(profit_sell, profit_buy, profit_nothing)\n",
    "        return dfs(0, 0, False)\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        days = len(prices)\n",
    "        if days < 1:\n",
    "            return 0\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(lambda :defaultdict(lambda: defaultdict(int)))\n",
    "        dp[0]['buy']['first'] = -prices[0]\n",
    "        dp[0]['buy']['second'] = -prices[0]\n",
    "        for day in range(1, days):\n",
    "            # first buy\n",
    "            dp[day]['buy']['first'] = max(dp[day-1]['buy']['first'], -prices[day])\n",
    "            # first sell\n",
    "            dp[day]['sell']['first'] = max(dp[day-1]['sell']['first'], dp[day-1]['buy']['first']+prices[day])\n",
    "            # second buy\n",
    "            dp[day]['buy']['second'] = max(dp[day-1]['buy']['second'], dp[day-1]['sell']['first']-prices[day])\n",
    "            # second sell\n",
    "            dp[day]['sell']['second'] = max(dp[day-1]['sell']['second'], dp[day-1]['buy']['second']+prices[day])\n",
    "\n",
    "        return  max(max(day_info['sell'].values()) for day_info in dp.values())\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        days = len(prices)\n",
    "        if days < 1:\n",
    "            return 0\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(lambda :defaultdict(lambda: defaultdict(int)))\n",
    "        dp[0]['buy']['first'] = -prices[0]\n",
    "        dp[0]['buy']['second'] = -prices[0]\n",
    "        res = 0\n",
    "        for day in range(1, days):\n",
    "            # first buy\n",
    "            dp[day]['buy']['first'] = max(dp[day-1]['buy']['first'], -prices[day])\n",
    "            # first sell\n",
    "            dp[day]['sell']['first'] = max(dp[day-1]['sell']['first'], dp[day-1]['buy']['first']+prices[day])\n",
    "            # second buy\n",
    "            dp[day]['buy']['second'] = max(dp[day-1]['buy']['second'], dp[day-1]['sell']['first']-prices[day])\n",
    "            # second sell\n",
    "            dp[day]['sell']['second'] = max(dp[day-1]['sell']['second'], dp[day-1]['buy']['second']+prices[day])\n",
    "            res = max(res, *dp[day]['sell'].values())\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.prices: Optional[List[int]] = None\n",
    "        self.dp = None\n",
    "\n",
    "    def GetRes(self, ownPrice, times, day) -> int:\n",
    "        if day >= len(self.prices):\n",
    "            return 0\n",
    "        if times >= 2:\n",
    "            return 0\n",
    "\n",
    "        if self.dp[ownPrice][times][day] != -1:\n",
    "            return self.dp[ownPrice][times][day]\n",
    "\n",
    "        if ownPrice == 1:\n",
    "            lhs = self.GetRes(ownPrice, times, day + 1)\n",
    "            rhs = self.GetRes(0, times + 1, day + 1) + self.prices[day]\n",
    "        else:\n",
    "            lhs = self.GetRes(ownPrice, times, day + 1)\n",
    "            rhs = self.GetRes(1, times, day + 1) - self.prices[day]\n",
    "\n",
    "        self.dp[ownPrice][times][day] = max(lhs, rhs)\n",
    "        return self.dp[ownPrice][times][day]\n",
    "\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        self.prices = prices\n",
    "        self.dp = [[[-1 for k in range(len(self.prices))] for j in range(2)] for i in range(2)]\n",
    "        return self.GetRes(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[-1 for _ in range(4)] for _ in range(len(prices))]\n",
    "        def dfs(idx, stat):\n",
    "            if idx == len(prices) or stat == 4: return 0\n",
    "            if dp[idx][stat] != -1: return dp[idx][stat]\n",
    "            if stat & 1 == 0:\n",
    "                dp[idx][stat] = max(dfs(idx + 1, stat), dfs(idx + 1, stat + 1) - prices[idx])\n",
    "            else:\n",
    "                dp[idx][stat] = max(dfs(idx + 1, stat), dfs(idx + 1, stat + 1) + prices[idx])\n",
    "            return dp[idx][stat]\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[n][k][0] = max(dp[n-1][k][0], dp[n-1][k][1] + price)\n",
    "        # dp[n][k][1] = max(dp[n-1][k][1], dp[n-1][k-1][0] - price)\n",
    "        dp = {}\n",
    "        maxK = 2\n",
    "        \n",
    "        for index, price in enumerate(prices):\n",
    "            dp[index] = {}\n",
    "\n",
    "            for k in range(maxK + 1):\n",
    "                dp[index][k] = {}\n",
    "\n",
    "                if index == 0:\n",
    "                    dp[index][k][0] = 0\n",
    "                    dp[index][k][1] = -price\n",
    "                    continue\n",
    "\n",
    "                if k == 0:\n",
    "                    dp[index][k][0] = 0\n",
    "                    dp[index][k][1] = -price\n",
    "                    continue\n",
    "\n",
    "                dp[index][k][0] = max(dp[index-1][k][0], dp[index-1][k][1] + price)\n",
    "                dp[index][k][1] = max(dp[index-1][k][1], dp[index-1][k-1][0] - price)\n",
    "        \n",
    "        return dp[len(prices) - 1][2][0]\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "                 \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[-1] * 4 for _ in range(len(prices))]\n",
    "        \n",
    "        def dfs(idx, s):\n",
    "            if idx == len(prices) or s == 4:\n",
    "                return 0\n",
    "            if dp[idx][s] != -1:\n",
    "                return dp[idx][s]\n",
    "            if s == 0 or s == 2:\n",
    "                dp[idx][s] = max(dfs(idx + 1, s), dfs(idx + 1, s + 1) - prices[idx])\n",
    "            else:\n",
    "                dp[idx][s] = max(dfs(idx + 1, s), dfs(idx + 1, s + 1) + prices[idx])\n",
    "            return dp[idx][s]\n",
    "        \n",
    "        return dfs(0, 0)\n",
    "        # dp = {}\n",
    "        # @lru_cache(maxsize=None)\n",
    "        # def dfs(index, state):\n",
    "        #     # state 有0买，1卖，2第二次买，3第三次卖，4停\n",
    "        #     if index >= len(prices) or state == 4: return 0\n",
    "        #     if state in [0, 2]:\n",
    "        #         dp[(index, state)] = max(dfs(index+1, state), dfs(index+1, state+1)-prices[index])\n",
    "        #     if state in [1, 3]:\n",
    "        #         dp[(index, state)] = max(dfs(index+1, state), dfs(index+1, state+1)+prices[index])\n",
    "        #     return dp[(index, state)]\n",
    "        # return dfs(0,0)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
